﻿module MinimumIndependentSet
    let ListContainsElem x list = 
        list |> Array.fold (fun acc elem -> acc || (elem = x)) false

    let FindLongestAugmentedPath (possibleMatches : int[][]) (vertex : int)= 
        let mutable possibleList = [| [| vertex |] |]
        let mutable iterations = possibleMatches.Length
        let mutable depthRemains = true
        while depthRemains && (iterations > 0) do
            iterations <- iterations - 1
            //let branchesToTest = possibleList |> Array.filter (fun i -> possibleMatches.[i].Length > 0)
                    
            //let permutations =[| for i in 0 .. possibleList.Length - 1 -> for j in 0 .. possibleList.[i].Length - 1 -> (i, j) |]
            let list = possibleList // Save the current instance of this mutable value
            
            // Enumerates all the permutations of matches
            let permutations =
                [| 0 .. list.Length - 1 |] |> Array.map (fun i ->
                    let route = list.[i]
                    if route.Length > 0 then
                        let last = route.[route.Length - 1]

                        // Excludes points already in the route
                        let nextMatches = possibleMatches.[last] |> Array.filter (fun elem -> not (route |> ListContainsElem elem))
                     //   printfn "->%d:%A" nextMatches.Length nextMatches

                        if nextMatches.Length > 0 then
                            [| 0 .. nextMatches.Length - 1 |] |> Array.map (fun j -> (i, j))
                        else
                            [| |]
                    else
                        [| |])
                |> Array.filter (fun x -> x.Length > 0)
                |> Array.collect (fun x -> x)

          //  printfn "%A" permutations

            depthRemains <- permutations.Length > 0
            if permutations.Length > 0 then
                // Auguments the routes with next possible matches
                possibleList <- permutations |> Array.map (fun p ->
                    let route = list.[fst p]
                    //printfn "%d;  %A" (fst i) route
                    if route.Length > 0 then
                        let last = route.[route.Length - 1]

                        // Excldes points already in the route
                        let nextMatches = possibleMatches.[last] |> Array.filter (fun elem -> not (route |> ListContainsElem elem))
                        Array.append route [| nextMatches.[snd p] |]
                        //Array.append route [| 0 |])
                    else
                        [|  |])
                |> Array.filter (fun x -> x.Length > 0)
        possibleList

    let MaximumMatching (left : int[][]) (right : int[][]) =
        let possibleMatches = Array.append (left |> Array.map (fun i -> i |> Array.map (fun j -> j + left.Length))) right
        let matches =
            [| 0 .. left.Length - 1 |] |> Array.map (fun i -> FindLongestAugmentedPath possibleMatches i |> Array.collect (fun x -> x))
            |> Array.collect (fun x -> x)
        //Brute force
        (*
        let permutations =
            [| 0 .. matches.Length - 1 |] |> Array.map (fun i ->
                [| 0 .. matches.[i].Length|] |> Array.map (fun j -> (i, j)))
            |> Array.collect (fun x -> x)

        
        let ApplyMatching (p : (int*int)[]) (matching : int[][]) =
            fst
            *)
        [| 0 .. left.Length - 1 |] |> Array.map (fun i ->
            [| 0 .. 2 .. matches.Length - 1 |] |> Array.fold (fun acc elem -> // Priortizes the last one
                if (matches.[elem] = i) && (elem < matches.Length - 1) then
                    matches.[elem + 1]
                else
                    acc) -1)
            //|> Array.map (fun i -> i - left.Length)

    let MinimumIndependentSet (left : int[][]) (right : int[][]) =
        let maxMatching = MaximumMatching left right
        [| 0 .. maxMatching.Length - 1 |]
            |> Array.map (fun i -> if maxMatching.[i] < 0 then i else maxMatching.[i])
            |> Array.sort